﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SimpleFormulaParser
{
    class Formula<T>
    {
        const int RulesCount = 10;
        public Func<string, T> ValueFromString;
        public Func<string, T, T, T> BinaryOperation;
        public Stack<object> ValueStack;
        public Stack<string> LLStack;
        public T Zero;

        List<char> KeySymbols = new List<char> { '+', '-', '*', '/', '(', ')' };

        public string[,] LLRules
            = new string[RulesCount, 3] { { "+", "Value", "Add" }, { "-", "Value", "Sub" } 
                ,{ "*", "Value", "Mul" },{ "/", "Value", "Div" }
                , { "Value", ")", "Rb" } ,{ "(", "Rb", "Value" }
                ,{ "Value", "Add", "Value" }, { "Value", "Sub", "Value" } 
            , { "Value", "Mul", "Value" } ,{ "Value", "Div", "Value" }
            
            };

        public T Calculation(string formula, Func<string, T> valueFromString,
            Func<string, T, T, T> binaryOperation)
        {
            BinaryOperation = binaryOperation;
            ValueFromString = valueFromString;

            int len = formula.Length;
            int i = 0;
            ValueStack = new Stack<object>();
            LLStack = new Stack<string>();
            Stack<bool> urgStack = new Stack<bool>();
            bool urg;
            bool br = false;
            char c = ' ';
            //bool urg = false;
            urgStack.Push(false);

            while (i < len)
            {
                c = formula[i];
                switch (c)
                {

                    case '-':
                        {
                            ShrinkStack();
                            if (br)
                            {
                                ValueStack.Push(Zero);
                                LLStack.Push("Value");
                            }
                            ValueStack.Push(null);
                            LLStack.Push(c.ToString());
                            br = false;
                            i++;
                            break;
                        }

                    case '+':
                        {
                            ShrinkStack();
                            ValueStack.Push(null);
                            LLStack.Push(c.ToString());
                            i++;
                            break;
                        }

                    case '(':
                        {
                            br = true;
                            ValueStack.Push(null);
                            LLStack.Push(c.ToString());
                            urgStack.Push(false);
                            i++;                            
                            break;
                        }

                    case '*':
                    case '/':
                        {
                            ValueStack.Push(null);
                            LLStack.Push(c.ToString());
                            urgStack.Pop();
                            urgStack.Push(true);
                            i++;
                            break;
                        }
                    case ')':
                        {
                            ShrinkStack();
                            ValueStack.Push(null);
                            LLStack.Push(c.ToString());
                            
                            urgStack.Pop();
                            urg = urgStack.Peek();
                            
                            CloseBrackets();
                            if (urg)
                            {
                                ShrinkStack();
                                urgStack.Pop();
                                urgStack.Push(false);
                            }
                           
                            i++;
                            break;
                        }

                    default:
                        {
                            // Getting the next value  
                            bool inl;
                            string value = "";
                            while ((i < len) && (!(inl = KeySymbols.Contains(c))))
                            {
                                if ((c != ' ') && (!inl))
                                    value += c;
                                i++;
                                c = (i < len)?formula[i]:' ';                                 
                            }
                            
                            if (value==string.Empty)
                                break;
                            br = false;
                            ValueStack.Push(ValueFromString(value));
                            LLStack.Push("Value");
                            urg = urgStack.Peek();                            
                            if (urg)
                            {
                                MulDiv();                                
                                urgStack.Pop();
                                urgStack.Push(false);
                            }
                            
                            break;
                        }
                        
                }
                urg = urgStack.Peek();                  
            }
            ShrinkStack();

            if (LLStack.Peek() == "Sub")
            {
                if (ValueStack.Count > 2)
                    throw new ParsingErrorException();
                return BinaryOperation(LLRules[7, 1], Zero, (T)ValueStack.Pop());
            }
            else
            {
                if (ValueStack.Count > 1)
                    throw new ParsingErrorException();
                return (T)ValueStack.Pop();
            }
            //MessageBox.Show(value
        }

        private void ShrinkStack()
        {
            bool isShrank = (LLStack.Count <= 1);
            if (isShrank)
                return;
            int ruleIdx = FindRule();
            while ((!isShrank) && (ruleIdx < RulesCount))
            {
                LLStack.Pop();
                LLStack.Pop();
                object rightValue = ValueStack.Pop();
                
                LLStack.Push(LLRules[ruleIdx, 2]);

                if (ruleIdx > 5)
                {
                    if ((ValueStack.Peek() != null) && (rightValue != null))
                    {
                        T leftValue = (T)ValueStack.Pop();
                        ValueStack.Push(BinaryOperation(LLRules[ruleIdx, 1], leftValue, (T)rightValue));
                    }
                }
                else
                {
                    ValueStack.Pop();
                    ValueStack.Push(rightValue);
                }
                isShrank = (LLStack.Count <= 1);
                if (!isShrank)
                    ruleIdx = FindRule();
            }
        }

        private void MulDiv()
        {
            bool isShrank = (LLStack.Count <= 1);
            if (isShrank)
                return;
            int ruleIdx = FindRule();
            int ruleIdxNext = ruleIdx + 6;
            if ((ruleIdx == 2) || (ruleIdx == 3))
            {
                LLStack.Pop();
                LLStack.Pop();
                LLStack.Push(LLRules[ruleIdx, 2]);

                object rightValue = ValueStack.Pop();
                ValueStack.Pop();
                ValueStack.Push(rightValue);

                isShrank = (LLStack.Count <= 1);
                if (!isShrank)
                    ruleIdx = FindRule();
            }

            if (isShrank)
                return;
            if (ruleIdx == ruleIdxNext)
            {
                LLStack.Pop();
                LLStack.Pop();
                object rightValue = ValueStack.Pop();

                LLStack.Push(LLRules[ruleIdx, 2]);                
                
                if ((ValueStack.Peek() != null) && (rightValue != null))
                {
                    T leftValue = (T)ValueStack.Pop();
                    ValueStack.Push(BinaryOperation(LLRules[ruleIdx, 1], leftValue, (T)rightValue));
                }                
            }
        }

        private void CloseBrackets()
        {
            bool isShrank = (LLStack.Count <= 1);
            if (isShrank)
                return;
            int ruleIdx = FindRule();
            if ((ruleIdx == 4))
            {
                LLStack.Pop();
                LLStack.Pop();  
                LLStack.Push(LLRules[ruleIdx, 2]);

                ValueStack.Pop();
                object leftValue = ValueStack.Pop();
                ValueStack.Push(leftValue);                
                
                isShrank = (LLStack.Count <= 1);
                if (!isShrank)
                    ruleIdx = FindRule();
            }
            
            if (isShrank)
                return;
            if ((ruleIdx == 5))
            {
                LLStack.Pop();
                LLStack.Pop();
                LLStack.Push(LLRules[ruleIdx, 2]);

                object rightValue = ValueStack.Pop();
                ValueStack.Pop();
                ValueStack.Push(rightValue);                
            }
        }

        private int FindRule()
        {
            // Get last pair at the top of stack
            IEnumerator<string> e = LLStack.GetEnumerator();
            e.MoveNext();
            string rs = e.Current;
            e.MoveNext();
            string ls = e.Current;
            // Find an according shrinking rule
            int i = 0;
            
            while ((i < RulesCount) && ((ls != LLRules[i, 0]) || (rs != LLRules[i, 1])))
                i++;
            return i;
        }
    }

    public class ParsingErrorException : System.Exception
    {
        public ParsingErrorException() : base() { }
        public ParsingErrorException(string message) : base(message) { }
        public ParsingErrorException(string message, System.Exception inner) : base(message, inner) { }
    }

}
